#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include<queue>
#include<set>
#include<unordered_set>
#define MOD 1000000007

struct my_struct
{
    int to;
    int en;
    int time;

    bool operator<(const my_struct& b) const
    {
        return time > b.time;
    }

    my_struct(int to, int en, int time)
        : to(to),
          en(en),
          time(time)
    {
    }
};

struct my_tu
{
    int to;
    int cost;

    my_tu(int to, int cost)
        : to(to),
          cost(cost)
    {
    }
};
class Solution
{
public:
    int electricCarPlan(std::vector<std::vector<int>>& paths, int cnt, int start, int end, std::vector<int>& charge)
    {
        int n = charge.size();
        std::vector<std::vector<my_tu>> tu(n,std::vector<my_tu>());
            int len = paths.size();
        for (int i = 0; i < len; i++)
        {
            tu[paths[i][0]].emplace_back(paths[i][1],paths[i][2]);
            tu[paths[i][1]].emplace_back(paths[i][0],paths[i][2]);
        }
        std::vector<std::vector<bool>> visited(n, std::vector<bool>(cnt+1, false));
        std::priority_queue<my_struct> pq;
        pq.emplace(start,0, 0);
std::vector<std::vector<int>> dis (n,std::vector<int>(cnt+1,std::numeric_limits<int>::max()));
        dis[start][0]=0;
        while (!pq.empty())
        {
            my_struct temp = pq.top();
            pq.pop();
            if (visited[temp.to][temp.en])
            {
               continue;
            }
            if (temp.to == end) return dis[end][temp.en];
            visited[temp.to][temp.en] = true;
            if (temp.en < cnt)
            {
                if (!visited[temp.to][temp.en + 1]&&dis[temp.to][temp.en+1] > dis[temp.to][temp.en]+charge[temp.to] )
                {
                    dis[temp.to][temp.en+1] = dis[temp.to][temp.en] + charge[temp.to];
                    pq.emplace(temp.to, temp.en+1,dis[temp.to][temp.en+1] );
                }
            }
            for (const auto next :tu[temp.to])
            {
                int cost = temp.en - next.cost;
                int time = temp.time + next.cost;
                if (cost < 0) continue;
                if (dis[next.to][cost] > time)
                {
                    dis[next.to][cost] = time;
                    pq.emplace(next.to, cost, dis[next.to][cost] );
                }
            }
        }
        return 0;
    }
};
